#include <iostream>
#include "BinaryTree.h"
using namespace std;

template <typename TreeType>
void testBinaryTree(int type)
{
    /*
     1:BinarySearchTree
     2:RedBlackTree
     3:AVLTree
     4:SplayTree
     */
    if(type==1){
        BinarySearchTree<int> t;
        int NUMS = 400000;
        const int GAP  =   3711;
        int i;

        cout << "Checking... (no more output means success)" << endl;

        for( i = GAP; i != 0; i = ( i + GAP ) % NUMS )
            t.insert( i );

        for( i = 1; i < NUMS; i+= 2 )
            t.remove( i );

        if( NUMS < 40 )
            t.printTree( );
        if( t.findMin( ) != 2 || t.findMax( ) != NUMS - 2 )
            cout << "FindMin or FindMax error!" << endl;

        for( i = 2; i < NUMS; i+=2 )
            if( !t.contains( i ) )
                cout << "Find error1!" << endl;

        for( i = 1; i < NUMS; i+=2 )
        {
            if( t.contains( i ) )
                cout << "Find error2!" << endl;
        }

        BinarySearchTree<int> t2;
        t2 = t;

        for( i = 2; i < NUMS; i+=2 )
            if( !t2.contains( i ) )
                cout << "Find error1!" << endl;

        for( i = 1; i < NUMS; i+=2 )
        {
            if( t2.contains( i ) )
                cout << "Find error2!" << endl;
        }

        cout << "Finished testing" << endl;
    }
    else if(type==2){
        const int NEG_INF = -9999;
        RedBlackTree<int> t{ NEG_INF };
        int NUMS = 400000;
        const int GAP  =   37;
        int i;

        cout << "Checking... (no more output means success)" << endl;

        for( i = GAP; i != 0; i = ( i + GAP ) % NUMS )
            t.insert( i );

        if( NUMS < 40 )
            t.printTree( );
        if( t.findMin( ) != 1 || t.findMax( ) != NUMS - 1 )
            cout << "FindMin or FindMax error!" << endl;

        for( i = 1; i < NUMS; ++i )
            if( !t.contains( i ) )
                cout << "Find error1!" << endl;
        if( t.contains( 0 ) )
            cout << "Oops!" << endl;

        
        RedBlackTree<int> t2{ NEG_INF };
        t2 = t;

        for( i = 1; i < NUMS; ++i )
            if( !t2.contains( i ) )
                cout << "Find error1!" << endl;
        if( t2.contains( 0 ) )
            cout << "Oops!" << endl;

        cout << endl << "Finished testing" << endl;
    }
    else if(type==3){
        AvlTree<int> t;
        int NUMS = 2000000;
        const int GAP  =   37;
        int i;

        cout << "Checking... (no more output means success)" << endl;

        for( i = GAP; i != 0; i = ( i + GAP ) % NUMS )
            t.insert( i );
        t.remove( 0 );
        for( i = 1; i < NUMS; i += 2 )
            t.remove( i );

        if( NUMS < 40 )
            t.printTree( );
        if( t.findMin( ) != 2 || t.findMax( ) != NUMS - 2 )
            cout << "FindMin or FindMax error!" << endl;

        for( i = 2; i < NUMS; i += 2 )
            if( !t.contains( i ) )
                cout << "Find error1!" << endl;

        for( i = 1; i < NUMS; i += 2 )
        {
            if( t.contains( i )  )
                cout << "Find error2!" << endl;
        }

        AvlTree<int> t2;
        t2 = t;

        for( i = 2; i < NUMS; i += 2 )
            if( !t2.contains( i ) )
                cout << "Find error1!" << endl;

        for( i = 1; i < NUMS; i += 2 )
        {
            if( t2.contains( i ) )
                cout << "Find error2!" << endl;
        }

        cout << "Finished testing" << endl;
    }
    else if(type==4){
        SplayTree<int> t;
        int NUMS = 30000;
        const int GAP  =   37;
        int i;

        cout << "Checking... (no more output means success)" << endl;

        for( i = GAP; i != 0; i = ( i + GAP ) % NUMS )
            t.insert( i );

        for( i = 1; i < NUMS; i+= 2 )
            t.remove( i );

        if( NUMS < 40 )
            t.printTree( );
        if( t.findMin( ) != 2 || t.findMax( ) != NUMS - 2 )
            cout << "FindMin or FindMax error!" << endl;

        for( i = 2; i < NUMS; i+=2 )
            if( !t.contains( i ) )
                cout << "Find error1!" << endl;

        for( i = 1; i < NUMS; i+=2 )
        {
            if( t.contains( i ) )
                cout << "Find error2!" << endl;
        }

        SplayTree<int> t2;
        t2 = t;

        for( i = 2; i < NUMS; i+=2 )
            if( !t2.contains( i ) )
                cout << "Find error1!" << endl;

        for( i = 1; i < NUMS; i+=2 )
        {
            if( t2.contains( i ) )
                cout << "Find error2!" << endl;
        }

        cout << endl << "Finished testing" << endl;
    }
}

// Test program
int main()
{
    /*
     1:BinarySearchTree
     2:RedBlackTree
     3:AVLTree
     4:SplayTree
     */
    cout<<"BinarySearchTree TEST"<<endl;
    testBinaryTree<int>(1);
    cout<<"---------------------"<<endl;
    cout<<"RedBlackTree TEST"<<endl;
    testBinaryTree<int>(2);
    cout<<"---------------------"<<endl;
    cout<<"AVLTree TEST"<<endl;
    testBinaryTree<int>(3);
    cout<<"---------------------"<<endl;
    cout<<"SplayTree TEST"<<endl;
    testBinaryTree<int>(4);
    cout<<"---------------------"<<endl;

    return 0;
}
